struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
/*
 * @lc app=leetcode.cn id=109 lang=cpp
 *
 * [109] 有序链表转换二叉搜索树
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    // 采用寻找中值的方法
    // TreeNode* sortedListToBST(ListNode* head) {
    //     return buildBST(head, nullptr);
    // }


    // // [ )
    // TreeNode* buildBST(ListNode* head, ListNode* tail) {
    //     if (tail == head) return nullptr;
    //     ListNode *slow = head, *fast = head;
    //     while (fast != tail) {
    //         fast = fast->next;
    //         if (fast == tail) break;
    //         fast = fast->next;
    //         slow = slow->next;
    //     }
    //     TreeNode* now = new TreeNode(slow->val);
    //     now->right = buildBST(slow->next, tail);
    //     now->left = buildBST(head, slow);
    //     return now;
    // }

    TreeNode* sortedListToBST(ListNode* head) {
        ListNode* cur = head; int len = 0;
        while (cur != nullptr) {
            len++; cur = cur->next;
        }
        return buildBST(head, 0, len - 1);
    }

    // [] 按照中序遍历的思路求解
    TreeNode* buildBST(ListNode* &head, int l, int r) {
        if (l > r) return nullptr; 
        int middle = (l + r) / 2;
        TreeNode *now = new TreeNode();
        now->left = buildBST(head, l, middle - 1);
        now->val = head->val;
        head = head->next;
        now->right = buildBST(head, middle + 1, r);
        return now;
    }
};
// @lc code=end

